package SwordOffer2;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;

public class day5_2 {
    /*
     * 双指针，HashMap，滑动窗口
     * 1.判断s与p长度，若s长度小于p长度，返回空
     * 2.创建两个HashMap，map1，map2；分别记录p，s的移动数组，(key，value)为(字母，字母重复次数)
     * 3.创建两个指针left，right构造滑动窗口，使窗口长度为s1长度，判断map1与map2包含(key，value)是否一致；
     *  若一致返回left，若不一致left，right右移，map2更新，添加right值或map2中right的value值加1，移除left值或者map2中left的value值减1
     * 4.res记录所有的满足条件的下标值left
     */
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> list = new LinkedList<>();
        if (s.length() < p.length()) {
            return list;
        }
        HashMap<Character, Integer> map1 = new HashMap<>();
        HashMap<Character, Integer> map2 = new HashMap<>();
        //保存s，p
        for (int i = 0; i < p.length(); i++) {
            if (map1.containsKey(p.charAt(i))) {
                map1.put(p.charAt(i), map1.get(p.charAt(i)) + 1);
            } else {
                map1.put(p.charAt(i), 1);
            }
            if (map2.containsKey(s.charAt(i))) {
                map2.put(s.charAt(i), map2.get(s.charAt(i)) + 1);
            } else {
                map2.put(s.charAt(i), 1);
            }
        }
/*        for (char c:map1.keySet()){
            System.out.print("key "+c+" value "+map1.get(c));
        }
        System.out.println("p");*/
        int left = 0;
        if (map1.equals(map2)) {
            list.add(left);
            //res = true;
        }
        for (int right = p.length(); right < s.length(); right++) {
/*            for (char c:map2.keySet()){
                System.out.print("key "+c+" value "+map2.get(c));
            }
            System.out.println();*/
            if (map2.containsKey(s.charAt(right))) {
                map2.put(s.charAt(right), map2.get(s.charAt(right)) + 1);
            } else {
                map2.put(s.charAt(right), 1);
            }
            if (map2.get(s.charAt(left)) > 1) {
                map2.put(s.charAt(left), map2.get(s.charAt(left)) - 1);
            } else {
                map2.remove(s.charAt(left));
            }
            left++;
            if (map1.equals(map2)) {
                // System.out.println("ll");
                list.add(left);
                //res = true;
            }

        }
/*                for (char c:map2.keySet()){
                System.out.print("key "+c+" value "+map2.get(c));
            }*/
        return list;
    }
}
